#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100010
using namespace std;
struct node
{
    int v,val,next;
}edge[3*MAXN];
int heads[MAXN],cnt,q[MAXN*5],d[MAXN],t[MAXN],n,k;
long long ans=0;
bool vis[MAXN];
void add(int x,int y,int z)
{
    edge[++cnt].v=y;
    edge[cnt].next=heads[x];
    heads[x]=cnt;
    edge[cnt].val=z;
}
bool SPFA()
{
    int head=1,tail=2;
    vis[0]=true;
    q[head]=0;
    t[0]=1;
    while(head<tail)
    {
        for(int i=heads[q[head]];i!=0;i=edge[i].next)
        {
            if(d[edge[i].v]<d[q[head]]+edge[i].val)
            {
                d[edge[i].v]=d[q[head]]+edge[i].val;
                if(!vis[edge[i].v])
                {
                    if(++t[edge[i].v]>=n)return false;
                    q[tail++]=edge[i].v;
                    vis[edge[i].v]=true;
                }
            }
        }
        vis[q[head]]=false;
        head++;
    }
    return true;
}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)
        {
            add(x,y,0);
            add(y,x,0);
        }
        else if(z==2)
        {
            if(x==y)
            {
                printf("-1\n");
                return 0;
            }
            else add(x,y,1);
        }
        else if(z==3)add(y,x,0);
        else if(z==4)
        {
            if(x==y)
            {
                printf("-1\n");
                return 0;
            }
            else add(y,x,1);
        }
        else if(z==5)add(x,y,0);
    }
    for(int i=n;i>=1;i--)add(0,i,1);
    if(!SPFA())
    {
        printf("-1\n");
        return 0;
    }
    for(int i=1;i<=n;i++)ans+=d[i];
    printf("%lld\n",ans);
    return 0;
}
